Matrix Multiplication Algorithm
Matrix multiplication is a fundamental operation in linear algebra, computer graphics, and various scientific simulations. The algorithm involves the multiplication of two matrices, where the number of columns in the first matrix must be equal to the number of rows in the second matrix. The resulting matrix, called the product matrix, is of size equal to the number of rows of the first matrix and the number of columns of the second matrix. This operation is not commutative, meaning that the order in which the matrices are multiplied affects the product matrix. Additionally, the algorithm does not satisfy the property of matrix element-wise multiplication; instead, it involves the dot product of the rows of the first matrix with the columns of the second matrix.
The matrix multiplication algorithm can be executed in a variety of ways, such as iterative methods, recursive methods, and parallel methods. The most common and straightforward approach is the iterative method, which comprises three nested loops. The outer two loops iterate through the rows and columns of the resulting matrix, while the innermost loop performs the dot product of the corresponding row from the first matrix and column from the second matrix. For each element in the product matrix, the dot product is calculated by multiplying the corresponding elements from the row and column and then summing up these products. The time complexity of this algorithm is O(n^3) for two n × n matrices. There are more efficient algorithms, such as Strassen's algorithm and the Coppersmith-Winograd algorithm, which can perform matrix multiplication in a faster time, but these methods are more complex and may not be practical for all applications.
/*
Petar 'PetarV' Velickovic
Algorithm: Matrix Multiplication
*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <complex>
using namespace std;
typedef long long lld;
/*
Naive algorithm for matrix multiplication of two matrices, A (of size n*l) and B (of size l*m).
Complexity: O(nlm)
*/
inline lld** MatrixMultiply(lld** a, lld** b, int n, int l, int m)
{
lld **c = new lld*[n];
for (int i=0;i<n;i++) c[i] = new lld[m];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
c[i][j]=0;
for(int k=0;k<l;k++)
{
c[i][j] += a[i][k]*b[k][j];
}
}
}
return c;
}
int main()
{
lld **matA;
matA = new lld*[2];
for (int i=0;i<2;i++) matA[i] = new lld[3];
matA[0][0] = 1;
matA[0][1] = 2;
matA[0][2] = 3;
matA[1][0] = 4;
matA[1][1] = 5;
matA[1][2] = 6;
lld **matB;
matB = new lld*[3];
for (int i=0;i<3;i++) matB[i] = new lld[2];
matB[0][0] = 7;
matB[0][1] = 8;
matB[1][0] = 9;
matB[1][1] = 10;
matB[2][0] = 11;
matB[2][1] = 12;
lld **matC = MatrixMultiply(matA, matB, 2, 3, 2);
for (int i=0;i<2;i++)
{
for (int j=0;j<2;j++)
{
printf("%lld ", matC[i][j]);
}
printf("\n");
}
return 0;
}
